import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 项目名称：wangxu
 * 类 名 称：hw239
 * 描 述：
 * 创建时间：2023/2/6 7:26 下午
 * 创 建 人：wang-xu
 */
public class hw239 {
    public static void main(String[] args) {
        int[] nums ={1,3,-1,-3,5,3,6,7};
        maxSlidingWindow(nums, 3);
    }

    public static int[] maxSlidingWindow(int[] nums, int k) {
        // 用于记录数组下标
        LinkedList<Integer> queue = new LinkedList<>();
        int length = nums.length;
        int[] ans = new int[length-k+1];
        // right为数组的下标
        for (int right = 0; right < length; right++) {
            // 后面的元素比队尾元素大或相等
            while (!queue.isEmpty() && nums[right] >= nums[queue.peekLast()]){
                // 移除队尾元素
                queue.removeLast();
            }
            queue.addLast(right);
            int left = right-k+1;
            // 左边界大于队首记录的下标，即窗口发生了移动
            if (queue.peekFirst()< left){
                queue.removeFirst();
            }
            // 左边界不小于0,取队首元素
            if(left>=0){
               ans[left] = nums[queue.peekFirst()];
            }
        }
        return ans;
    }
}
